package a_erfenchazhao.lianxiti;

import java.util.Arrays;

/**
 * @ClassName SouSuoKaiShiHeJieShuWeiZhi
 * @Description
 * @Author Zhang Li Tao
 * @Date 2024/3/21
 * @Version 1.0
 **/
public class SouSuoKaiShiHeJieShuWeiZhi {
    /**
     * 示例 1：
     *
     * 输入：nums = [5,7,7,8,8,10], target = 8
     * 输出：[3,4]
     * 示例 2：
     *
     * 输入：nums = [5,7,7,8,8,10], target = 6
     * 输出：[-1,-1]
     * 示例 3：
     *
     * 输入：nums = [], target = 0
     * 输出：[-1,-1]
     */

    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 5, 5, 6};
        int target = 7;

        System.out.println(Arrays.toString(searchRange(nums, target)));
    }

    // 先leftMost最左边的 再rightMost最右边的 这里只是找位置 并非应用写法 寻找插入点
    public static int[] searchRange(int[] nums, int target) {
        int[] resultArray = new int[2];

        // leftMost 如果为-1 则说明没有目标值 直接返回 [-1, -1]
        int leftIndex = 0;
        int rightIndex = nums.length - 1;

        int resultIndex = -1;

        while (leftIndex <= rightIndex) {
            int middleIndex = (leftIndex + rightIndex) >>> 1;

            if (target < nums[middleIndex]) {
                rightIndex = middleIndex - 1;
            } else if (nums[middleIndex] < target) {
                leftIndex = middleIndex + 1;
            } else {
                resultIndex = middleIndex;
                rightIndex = middleIndex - 1;
            }
        }

        if (resultIndex == -1) {
            return new int[]{-1, -1};
        }

        resultArray[0] = resultIndex;

        // 开始处理rightMost
        leftIndex = 0;
        rightIndex = nums.length - 1;

        while (leftIndex <= rightIndex) {
            int middleIndex = (leftIndex + rightIndex) >>> 1;

            if (target < nums[middleIndex]) {
                rightIndex = middleIndex - 1;
            } else if (nums[middleIndex] < target) {
                leftIndex = middleIndex + 1;
            } else {
                resultIndex = middleIndex;
                leftIndex = middleIndex + 1;
            }
        }

        resultArray[1] = resultIndex;

        return resultArray;
    }


}
